/*************************************************************************
 * File Name:    Sqrtx.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/4 12:49:05
 * 
 * Description:  
 |-----------------------------------------------------------------------
 | Problem: Sqrt(x)
 | Implement int sqrt(int x).
 | Compute and return the square root of x.
 |-----------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    int sqrt(int x)
    {
        if (x <= 0) return 0;
        long long left, right, mid;
        long long ans;
        
        ans = left = 1, right = x;
        while (left <= right) {
            mid = (right - left) / 2 + left;
            
            if (mid * mid > x) {
                right = mid - 1;
            } else {
                ans = mid;
                left = mid + 1;
            }
        }
        return ans;
    }
};

